package com.wngbms.zuochengyun;

public class FastSlowPointer {

    static class Node<T> {
        T value;
        volatile Node<T> next;

        public Node(T value) {
            this.value = value;
        }

        public Node<T> setNext(Node<T> next) {
            this.next = next;
            return this;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    static Node<String> find(Node<String> head) {
        if (head == null) {
            return null;
        }

        Node<String> fastPointer = head;
        Node<String> slowPointer = head;

        do {
            if (slowPointer == null
                    || fastPointer == null
                    || fastPointer.next == null) {
                return null;
            }

            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;

        } while (fastPointer != slowPointer);

        fastPointer = head;

        do {
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next;

        } while (fastPointer != slowPointer);

        return fastPointer;
    }

    public static void main(String[] args) {

        Node<String> a = new Node<>("A");
        Node<String> b = new Node<>("B");
        Node<String> c = new Node<>("C");
        Node<String> d = new Node<>("D");
        Node<String> e = new Node<>("E");
        Node<String> f = new Node<>("F");
        Node<String> g = new Node<>("G");
        Node<String> h = new Node<>("H");

        a.setNext(b);
        b.setNext(c);
        c.setNext(d);
        d.setNext(e);
        e.setNext(f);

        f.setNext(g);
        g.setNext(h);
//        h.setNext(e);

        System.out.println(find(a));

    }
}
